package com.naokeziteng.dijkstra.algorithm;

import com.naokeziteng.dijkstra.domain.Graph;

import java.util.*;

/**
 * @author hawk
 * @date 2022/10/13
 * @desc Dijkstra最短路径
 **/
public class Dijkstra {
    //起点
    private String start;
    //终点
    private String end;
    //图
    private Graph G;
    //是否被访问过
    private TreeSet<String> visited;
    //源点到每个节点的路径
    private TreeMap<String, Double> dis;
    //上一个节点的下标
    private TreeMap<String, String> pre;


    private class Node implements Comparable<Node> {
        public String v;
        public double dis;

        public Node(String v, double dis) {
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node o) {
            return Double.compare(dis, o.dis);
        }
    }


    public Dijkstra(Graph G, String start, String end) {
        this.G = G;
        this.start = start;
        this.end = end;
        this.pre = new TreeMap<>();
        this.dis = new TreeMap<>();
        this.visited = new TreeSet<>();

        //优先队列
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start, 0));

        //设置源点距离
        dis.put(start, 0d);
        pre.put(start, start);
        while (!queue.isEmpty()) {
            //当前dis值最小的节点
            String cur = queue.remove().v;
            //已经被处理过，直接跳过
            if (visited.contains(cur)) {
                continue;
            }

            visited.add(cur);
            //终点最短距离已找到，终止循环
            if (cur.equals(end)) {
                break;
            }
            for (String w : G.adj(cur)) {
                if (!visited.contains(w)) {
                    double weight = G.getWeight(cur, w) + dis.get(cur);
                    if (dis.get(w) == null || weight < dis.get(w)) {
                        dis.put(w, weight);
                        pre.put(w, cur);
                        queue.add(new Node(w, weight));
                    }
                }
            }
        }


    }

    public boolean isConnected() {
        return visited.contains(end);
    }

    //寻找单源路径
    public List<String> path() {
        List<String> result = null;
        if (!isConnected()) {
            return result;
        }
        result = new ArrayList<>();
        String p = end;
        while (!p.equals(start)) {
            result.add(p);
            p = pre.get(p);
        }
        result.add(start);
        Collections.reverse(result);
        return result;
    }

}
